1. Field of the Invention
The present invention relates to a iterative decoding method for a concatenated code or a product code, and an iterative decoding apparatus therefor.
2. Description of the Related Art
A concatenated code is a code in which two different codes of an outer code and an inner code are concatenated. It is known that by alternately and iteratively performing a decoding process for an inner code and a decoding process for an outer code a plurality of times, an error correction ability of the concatenated code is improved. FIG. 1 is schematic diagram showing an example of a structure of a conventional iteratively decoding circuit.
In FIG. 1, received data R is decoded by a first stage decoder 101. The first stage decoder 101 corrects errors of the received data R. The resultant error corrected data DI1 is deinterleaved by a first stage deinterleaver 102. The resultant deinterleaved data Ddeint1 is decoded by a first stage outer code decoder 103. The first stage outer code decoder 103 corrects errors which were not corrected by the first stage decoder 101. The resultant error corrected data DO1 is interleaved by a first stage interleaver 104. The resultant interleaved data Dint1 is decoded by a second stage inner code decoder 105. The second stage inner code decoder 105 corrects errors which was not corrected by the first stage outer code decoder 103. The resultant error corrected data DI2 is deinterleaved by a second stage deinterleaver 106. The resultant deinterleaved data Ddeint2 is decoded by a second stage outer code decoder 107. The second stage stage inner code decoder 105. The resultant error corrected data DO2 is output.
In a iteratively decoding circuit, an inner code decoder iteratively performs an inner code decoding process for received data and an outer code decoder iteratively performs an outer code decoding process for the data decoded by the inner code decoder. The foregoing decoding circuit iteratively performs the inner code decoding process and the outer code decoding process two times each. The decoding circuit may iteratively perform those processes three or more times each.
Next, a product code that is one type of a concatenated code will be described. FIG. 2 is a schematic diagram showing an example of a product code. Referring to FIG. 2, check symbols for a product code are added to information symbols. In FIG. 2, encoded data is composed of M×N symbols (where M and N are positive integers). Of the M×N symbols, MO×NO symbols are information symbols. The portion excluding the information symbols is composed of check symbols.
A product code is a code in which two different codes are vertically and horizontally interleaved, respectively. In other words, a product code is composed of two error correction codes arranged in different directions of horizontal and vertical directions. In contrast, with the foregoing concatenated code, any interleaving method can be used.
In the example shown in FIG. 2, the product code is composed of outer code symbols PO1 to PON0 with which information symbols are encoded in the vertical direction and inner code symbols PI1 to PIM with which the information symbols are encoded in the horizontal direction. One column of the product code corresponds to one code word of the outer code PO, whereas one row of the product code corresponds to one code word of the inner code PI.
As an error correction code, a block code such as a Reed-Solomon (RS) code and a Bose-Chaudhuri-Hocquenghem (BCH) code is used. The product code decoder performs a decoding process (an error correcting process) by iteratively correcting errors of data encoded with a block in two directions.
Next, a conventional concatenated code decoding method will be described with an example of a decoding circuit for a product code that is one type of a concatenated code.
FIG. 3 is a flow chart showing an example of a conventional iteratively product code decoding process. Referring to FIG. 3, first of all, the number of loop times (loop count) is reset to zero (at step S101). Thereafter, errors of code words of the inner code PI sequence are successively corrected (at step S102). Thereafter, errors of code words of the outer code PO sequence are successively corrected (at step S103). Thereafter, the loop counter is incremented by one (at step S104). Thereafter, it is determined whether or not the value of the loop counter matches the predetermined number of loop times (at step S105). If the value of the loop counter does not match the predetermined number of loop times (determined result is NO), then steps S102 to S104 are iterated. In contrast, if the value of the loop counter matches the predetermined number of loop times (determined result is YES), then the decoding process is completed.
In such a manner, errors of code words of the inner code PI sequence and errors of code words of the outer code PO sequence are iteratively corrected a plurality of times. This is because the maximum number of error symbols which can be corrected in the error correcting process for each code word is limited. Error symbols are corrected in the range which does not exceed the number of correctable symbols. By iteratively performing the error correcting process for each sequence, error symbols of information symbols are gradually corrected. It is known that as the number of times the error correcting process is iteratively performed is large, the number of error symbols which can be corrected becomes large.
An example of such a product code decoding circuit is described in Japanese Patent Laid-Open Publication No. 2000-101447 (paragraphs [0026] to [0030], FIG. 1) (hereinafter referred to as patent document 1). FIG. 4 is a schematic diagram showing a structure of a product code decoding circuit 200 described in the parent document 1. Referring to FIG. 4, the product code decoding circuit 200 comprises a code input/output circuit 201, a line buffer 202, an error correcting circuit 203, a controller 204, and a correction status storing circuit 205.
In addition, the error correcting circuit 203 comprises a syndrome calculating circuit 211, an error locator polynomial/error value polynomial calculating circuit 212, an error position detecting/correcting circuit 213, an error locator polynomial degree/detected number-of-errors comparing circuit 214. In FIG. 4, reference numeral 300 represents a buffer memory which is an external unit which transmits and receives data to and from the code input/output circuit 201.
The product code decoding circuit 200 corrects error symbols of each code word of each of the PI sequence (inner code) and PO sequence (outer code). The correction status storing circuit 205 stores results of corrected error symbols. The controller 204 references a correction flag stored in the correction status storing circuit 205 so as to perform the error correcting process for code words which have error symbols and skip the error correcting process for code words which do not have error symbols and code words whose error symbols have been already corrected. As a result, the number of code words subjected to the correcting process is decreased and the calculation amount of the error correcting process is decreased.
Next, assuming that the number of iterative times of the error correcting process of the product code decoding circuit 200 is two, with reference to FIG. 5 and FIG. 6, an operation of the circuit will be described in brief. FIG. 5 is a schematic diagram showing a structure of the product code decoding circuit 200. FIG. 6 is a flow chart showing the operation of the product code decoding circuit 200. Referring to FIG. 5, the product code decoding circuit 200 comprises a first stage inner code decoder 221, a first stage outer code decoder 222, a second stage inner code decoder 223, and a second stage outer code decoder 224.
The first stage inner code decoder 221, the first stage outer code decoder 222, the second stage inner code decoder 223, and the second stage outer code decoder 224 shown in FIG. 5 are disposed in the error correcting circuit 203 shown in FIG. 4. These units are controlled by the controller 204 shown in FIG. 4. A residual error flag which will be described later is stored in the correction status storing circuit 205 shown in FIG. 4.
The first stage inner code decoder 221 divides the received data R into inner code words PI1 to PIM. If the number of error symbols per code word does not exceed the error correctable range, then the first stage inner code decoder 221 performs the error correcting process for the error symbols and outputs the resultant error corrected data DI1 to the next stage. In addition, the first stage inner code decoder 221 determines whether or not the error correcting process has failed for error symbols of each of the inner code words PI1 to PIM because the number of error symbols exceeds the error correctable range and outputs a residual error flag REFI which represents whether the error correcting process has failed to the second stage inner code decoder 223 (at step S111).
The first stage outer code decoder 222 divides the error corrected data DI1 into outer code words PO1 to PON0. If the number of error symbols per code word does not exceed the error correctable range, then the first stage outer code decoder 222 performs the error correcting process for error symbols of each inner code word and outputs the resultant error corrected data DO1 to the next stage. In addition, the first stage outer code decoder 222 determines whether or not the error correcting process has failed for error symbols of each of the outer code words PO1 to PON0 because the number of error symbols exceeds the error correctable range and outputs a residual error flag REFO which represents whether or not the error correcting process has failed to the second stage outer code decoder 224 (at step S112).
The second stage inner code decoder 223 divides the error corrected data DO1 into inner code words PI1 to PIM. If the number of error symbols per code word does not exceed the error correctable range, then the second stage inner code decoder 223 performs the error correcting process for error symbols of each of the inner code words PI1 to PIM and outputs the resultant error corrected data DI2 to the next stage. However, the second stage inner code decoder 223 skips the error correcting process for each inner code word which does not have error symbols in accordance with the residual error flag REFI (at step S113). In other words, the second stage inner code decoder 223 performs the error correcting process for all inner code words for which the residual error flag REFI is set. However, the second stage inner code decoder 223 does not perform the error correcting process for all inner code words for which the residual error flag REFI is reset. Thus, the second stage inner code decoder 223 determines whether or not to perform the error correcting process for each code word depending on whether or not the residual error flag REFI is set therefor.
The second stage outer code decoder 224 separates the error corrected data DI2 into outer code words PO1 to PON0. When the number of error symbols per each code word does not exceed the error correctable range, the second stage outer code decoder 224 performs the error correcting process for error symbols of each code word and outputs the resultant error corrected data DO2. However, the second stage outer code decoder 224 skips the error correcting process for each outer code word which does not have error symbols in accordance with the residual error flag REFO (at step S114). In other words, the second stage outer code decoder 224 performs the error correcting process for all outer code words for which the residual error flag REFO is set. In contrast, the second stage outer code decoder 224 does not perform the error correcting process for all outer code words for which the residual error flag REFO is reset. Thus, the second stage outer code decoder 224 determines whether or not to perform the error correcting process for each outer code depending on whether or not the residual error flag REFO is set therefor.
According to the related art reference, by referencing the residual error flags REFI and the REFO, the error correcting process is performed for only code words which have error symbols. However, the error correcting process is skipped for code words which do not have error symbols and code words for which the error correcting process has been already performed. Thus, the number of code words for which the error correcting process is performed is decreased and the calculation amount for the error correcting process is decreased.
In consideration of inner code words, the error correcting process can be skipped for the following two types thereof.
(1) an inner code word whose error symbols have been corrected by immediately preceding stage inner code decoding process or former decoding process and an inner code word who has no error symbols from the first.
(2) an inner code word which had error symbols which exceed the error correctable range for the immediately preceding stage inner code decoding process, and whose number of errors was not decreased by the immediately preceding stage inner code decoding process. Since this inner code word has error symbols which exceed the error correctable range, it is meaningless to perform the decoding process for this inner code word.
Likewise, in consideration of outer code words, the error correcting process can be skipped for the following two types thereof.
(3) an outer code word whose error symbols have been corrected by immediately preceding stage outer code decoding process or former decoding process and an outer code word who has no error symbols from the first.
(4) an outer code word which had error symbols which exceed the error correctable range for the immediately preceding stage outer code decoding process, and whose number of errors was not decreased by the immediately preceding stage outer code decoding process. Since this outer code word has error symbols which exceed the error correctable range, it is meaningless to perform the decoding process for the outer code word.
However, according to the related art reference, since the error correcting process is skipped for only the foregoing cases (1) and (3), the effect that the calculation amount is decreased is low.